package com.查找算法;


class Solution4 {
    //法一:顺序遍历查找
    public int missingNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=i) return i;

        }
        return nums.length;
    }
    //法二：二分查找
    public int missingNumber2(int[] nums) {
       int len=nums.length;
       int i=0,j=len-1;
       while(i<=j){
           //int m=(i+j)/2;//这种写法可能会溢出
           int m=i+(j-i)/2;//这种写法可以防止溢出
           if(nums[m]==m) i=m+1;
           else j=m-1;
       }
       return i;
    }
}
public class 剑指Offer55I缺失的数字 {
    public static void main(String[] args) {

    }
}
